1519. Коды Грея

 

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность

0

1

-

Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:

00
01
11
10

Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение.

000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4

Приведенные последовательности называются кодами Грея длины n = 1, 2, 3. Всего существует 2n разных кодов длины n. Каждые два соседних кода отличаются одним битом.

 

Вход. Первая строка содержит количество тестов t (t £ 250000). Каждая следующая строка содержит два числа: n (1 £ n £ 30) и k (0 £ k < 2n).

 

Выход. Для каждого теста в отдельной строке выведите число, которое находится в k - ой позиции последовательности кодов Грея длины n.

 

Пример входа

Пример выхода

14

1 0

1 1

2 0

2 1

2 2

2 3

3 0

3 1

3 2

3 3

3 4

3 5

3 6

3 7

0

1

0

1

3

2

0

1

3

2

6

7

5

4

 

 

РЕШЕНИЕ

рекурсия + комбинаторика

 

Анализ алгоритма

Запишем рекурсивную функцию find(n, k), которая будет находить число в k - ой позиции последовательности кодов Грея длины n. Если значение k лежит в первой части последовательности (k < 2n-1, так как позиции нумеруются с нуля), то следует искать число, стоящее в k - ой позиции кодов Грея длины n – 1. Иначе воспользуемся симметрией при построении кодов Грея: результат будет равен 2n-1 плюс число, стоящее в (2n –  k – 1) - ой позиции кодов Грея длины n – 1.

Таким образом find(n, k) =

 

Пример

 

Реализация алгоритма

Функция find(n, k) находит число, которое находится в k - ой позиции последовательности кодов Грея длины n.

 

int find(int n, int k)

{

  if (!n) return 0;

  int temp = 1 << (n-1);

  if (k < temp) return find(n-1,k);

  return temp + find(n-1, (1 << n) - 1 - k);

}

 

Основной цикл программы. Читаем количество тестов tests. Для каждого теста читаем входные данные n и k. Вычисляем и выводим значение find(n, k).

 

  scanf("%d",&tests);

  while(tests--)

  {

    scanf("%d %d",&n,&k);

    res = find(n,k);

    printf("%d\n",res);

  }

 

Java реализация

 

import java.util.*;

 

public class Main

{

  static int find(int n, int k)

  {

    if (n == 0) return 0;

    int temp = 1 << (n-1);

    if (k < temp) return find(n-1,k);

    return temp + find(n-1, (1 << n) - 1 - k);

  }

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int tests = con.nextInt();

    while(tests-- > 0)

    {

      int n = con.nextInt(), k = con.nextInt();

      int res = find(n,k);

      System.out.println(res);

    }

  }

}